{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "逃逸者被捕获，共进行了0步。\n"
     ]
    }
   ],
   "source": [
    "class ChaseEscapeGame:\n",
    "    def __init__(self, escaper_start, chaser_start):\n",
    "        self.escaper_position = escaper_start\n",
    "        self.chaser_position = chaser_start\n",
    "        self.steps = 0\n",
    "\n",
    "    def is_captured(self):\n",
    "        return self.chaser_position >= self.escaper_position\n",
    "\n",
    "    def move_escaper(self, action):\n",
    "        if action == 'move':\n",
    "            self.escaper_position += 1\n",
    "        # 如果action不是'move'，则逃逸者保持不动\n",
    "\n",
    "    def move_chaser(self, action):\n",
    "        if action == 'move':\n",
    "            self.chaser_position += 1\n",
    "        # 如果action不是'move'，则追逐者保持不动\n",
    "\n",
    "    def play_game(self, escaper_strategy, chaser_strategy):\n",
    "        while not self.is_captured():\n",
    "            self.move_escaper(escaper_strategy(self.escaper_position, self.chaser_position))\n",
    "            self.move_chaser(chaser_strategy(self.escaper_position, self.chaser_position))\n",
    "            self.steps += 1\n",
    "        return self.steps\n",
    "\n",
    "# 示例策略：逃逸者总是移动，追逐者总是移动\n",
    "def escaper_strategy(escaper_pos, chaser_pos):\n",
    "    return 'move'\n",
    "\n",
    "def chaser_strategy(escaper_pos, chaser_pos):\n",
    "    return 'move'\n",
    "\n",
    "# 创建游戏实例并运行\n",
    "game = ChaseEscapeGame(0,1)  # 逃逸者从0开始，追逐者从2开始\n",
    "steps_to_capture = game.play_game(escaper_strategy, chaser_strategy)\n",
    "print(f\"逃逸者被捕获，共进行了{steps_to_capture}步。\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "剪枝优化\n",
    "\n",
    "**博弈树的概念**：\n",
    "\n",
    "* 博弈树是由于动态博弈参与者的行动有先后次序，因此可以依次将参与者的行动展开成一个树状图形。它是扩展型博弈的一种形象化表述，能给出有限博弈的几乎所有信息。\n",
    "* 博弈树的基本构建材料包括结、枝和信息集。其中，结分为决策结和终点结两类；决策结是参与人采取行动的时点，终点结是博弈行动路径的终点。枝是从一个决策结到它的直接后续结的连线，每一个枝代表参与人的一个行动选择。\n",
    "\n",
    "**博弈树与博弈论的关系**：\n",
    "\n",
    "* 博弈树是博弈论中分析序贯博弈的一种有效工具。在序贯博弈中，博弈参与者按照某个特定的顺序采取行动，这种博弈可以通过博弈树来清晰地表示。\n",
    "* 博弈树能够展示博弈过程中所有可能的行动路径和结果，帮助参与者做出最优决策。\n",
    "\n",
    "**博弈树的剪枝问题**：\n",
    "\n",
    "* 在构建和分析博弈树时，确实存在剪枝问题。由于博弈树可能非常庞大和复杂，包含大量的节点和分支，因此需要通过剪枝来简化树的结构，提高决策效率。\n",
    "* 一种常见的剪枝方法是α-β剪枝算法。这种算法通过评估不同行动路径的优劣来裁剪掉那些明显不可能成为最优解的分支，从而减少搜索空间，加速决策过程。\n",
    "* α-β剪枝算法基于极大极小搜索原理，在搜索过程中不断更新α（最大值的下界）和β（最小值的上界）值来裁剪无效的搜索分支。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最优情况下，逃逸者可以在-1步内不被捕获。\n"
     ]
    }
   ],
   "source": [
    "class ChaseEscapeGame:  \n",
    "    def __init__(self, escaper_start, chaser_start, max_depth):  \n",
    "        self.escaper_position = escaper_start  \n",
    "        self.chaser_position = chaser_start  \n",
    "        self.max_depth = max_depth  \n",
    "  \n",
    "    def is_terminal(self, depth):  \n",
    "        return depth == self.max_depth or self.chaser_position >= self.escaper_position  \n",
    "  \n",
    "    def move_escaper(self):  \n",
    "        self.escaper_position += 1  \n",
    "  \n",
    "    def move_chaser(self):  \n",
    "        self.chaser_position += 1  \n",
    "  \n",
    "    def minimax(self, depth, is_max_player, alpha, beta):  \n",
    "        if self.is_terminal(depth):  \n",
    "            # 如果逃逸者被捕获，返回-1（表示失败），否则返回当前深度（表示逃逸的步数）  \n",
    "            return -1 if self.chaser_position >= self.escaper_position else depth  \n",
    "  \n",
    "        if is_max_player:  \n",
    "            max_eval = float('-inf')  \n",
    "            for _ in range(2):  # 追逐者可以选择移动或不动  \n",
    "                self.move_chaser()  \n",
    "                eval = self.minimax(depth + 1, False, alpha, beta)  \n",
    "                self.chaser_position -= 1  # 回溯  \n",
    "                max_eval = max(max_eval, eval)  \n",
    "                alpha = max(alpha, eval)  \n",
    "                if beta <= alpha:  \n",
    "                    break  # β剪枝  \n",
    "            return max_eval  \n",
    "        else:  \n",
    "            min_eval = float('inf')  \n",
    "            for _ in range(2):  # 逃逸者可以选择移动或不动  \n",
    "                self.move_escaper()  \n",
    "                eval = self.minimax(depth + 1, True, alpha, beta)  \n",
    "                self.escaper_position -= 1  # 回溯  \n",
    "                min_eval = min(min_eval, eval)  \n",
    "                beta = min(beta, eval)  \n",
    "                if beta <= alpha:  \n",
    "                    break  # α剪枝  \n",
    "            return min_eval  \n",
    "  \n",
    "# 创建游戏实例  \n",
    "game = ChaseEscapeGame(0, 2, 5)  # 逃逸者从0开始，追逐者从2开始，最大深度为5  \n",
    "  \n",
    "# 运行极小极大搜索算法，并应用α-β剪枝  \n",
    "result = game.minimax(0, True, float('-inf'), float('inf'))  \n",
    "print(f\"最优情况下，逃逸者可以在{result}步内不被捕获。\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "develop",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
